package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/plus-one-linked-list'>给单链表加一(Plus One Linked List)</a>
 * <p>给定一个用链表表示的非负整数， 然后将这个整数 再加上 1 。</p>
 * <p>这些数字的存储是这样的：最高位有效的数字位于链表的首位 head 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1:
 *      输入: head = [1,2,3]
 *      输出: [1,2,4]
 *
 *  示例 2:
 *      输入: head = [0]
 *      输出: [1]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表中的节点数在 [1, 100] 的范围内。</li>
 *     <li>0 <= Node.val <= 9</li>
 *     <li>由链表表示的数字不包含前导零，除了零本身。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/14 14:11
 */
public class LC0369PlusOneLinkedList_M {
    static class Solution {
        public ListNode plusOne(ListNode head) {
            //return recursion(head) ? new ListNode(1, head) : head;
            return iteration(head);
        }

        private ListNode iteration(ListNode head) {
            /*
               思路：找出链表中，最右侧不为9的节点，即为notNineNode，
                    1.不存在值不为9的节点，需要添加新的表头，值为1。将后续所有值为9的节点值置为0
                    2.存在置为不为9的节点，将其值+1。将后续所有值为9的节点值置为0
            */
            ListNode notNineNode = null;
            ListNode currNode = head;
            while (currNode != null) {
                if (currNode.val != 9) {
                    notNineNode = currNode;
                }
                currNode = currNode.next;
            }
            // 说明所有的节点值都是9，此时需要添加新表头
            if (notNineNode == null) {
                head = new ListNode(1, head);
                currNode = head.next;
            } else {
                // 存在非9的元素，使其值+1
                notNineNode.val += 1;
                currNode = notNineNode.next;
            }
            // 将后续所有值为9的节点置为0
            while (currNode != null) {
                currNode.val = 0;
                currNode = currNode.next;
            }
            return head;
        }

        private boolean recursion(ListNode currNode) {
            if (currNode == null) {
                return false;
            }
            // 若为末尾节点，直接加一
            if (currNode.next == null) {
                currNode.val += 1;
            }
            // 如果不是末尾节点，递归处理后续节点，并根据结果更新当前节点
            else {
                boolean carry = recursion(currNode.next);
                // 如果递归处理后续节点返回true，说明有进位，当前节点值需要+1；否则无需处理
                if (carry) {
                    currNode.val += 1;
                }
            }
            // 判断当前节点是否需要进位
            if (currNode.val > 9) {
                currNode.val %= 10;
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.plusOne(Generator.create(1, 2, 3)));
        Printer.printListNode(solution.plusOne(Generator.create(0)));
        Printer.printListNode(solution.plusOne(Generator.create(9, 9, 9, 9)));
    }
}
